package com.heima.leetcode.datastructure.heap;

/**
 * <strong>找到数组中第k大的元素 215</strong>
 * <ul>
 *     <li>建立一个k大小的小顶堆</li>
 *     <li>遍历数组元素：
 *         <ol>
 *             <li>如果堆未满，则直接加入到堆中</li>
 *             <li>如果堆为满，让遍历到的元素和堆顶元素比较</li>
 *             <li>如果遍历到的元素 < 堆顶元素，则跳过</li>
 *             <li>如果遍历到的元素 > 堆顶元素，则替换堆顶元素重构</li>
 *         </ol>
 *     </li>
 *     <li>遍历结束后，小顶堆的堆顶元素就是数组中第k个大的元素</li>
 * </ul>
 * @author 勾新杰
 * @version 1.0
 * @date 2024/9/6 16:58
 */
public class FindKthLargest {
    public static int findKthLargest(int[] arr, int k){
        MinHeap heap = new MinHeap(k);
        for (int i = 0; i < k; i++) {
            heap.offer(arr[i]);
        }
        for (int i = k; i < arr.length; i++){
            if (arr[i] > heap.peek()){
                heap.replace(arr[i]);
            }
        }
        return heap.peek();
    }
}
